Modern computer networks are configured as an interconnection of many computer systems links by a set of interconnected data communications devices or nodes such as routers, switches, and gateways. The links between the computers and data communications devices may be physical network cables or wireless links. Typically, a network administrator configures each of the computers and data communications devices in the network with a respective network address. A computer that needs to transmit data to a remote computer across the network creates a series of packets for the data. Each packet includes header information that contains a source network address (e.g. an Internet Protocol or IP address) of the computer originating the packet, as well as a destination address of the computer or other device that is to receive the packet. Other information may be contained in the header as well.
To send a packet to the remote destination computer, the source computer transmits the packet to the first data communications device coupling that source computer to the network. This device, which is commonly a router or switch, is the first node or hop on the network. The device examines the packet header to determine where to next transmit the packet based on the destination address encoded within the packet header. Upon determining on which route to send the packet, the device forwards or retransmits the packet to the next hop thus moving the packet across the network further towards its destination. Each data communications device in the network operates in a similar manner such that the packet eventually reaches its intended destination.
Long ago in computer networking, it was discovered that network loops might occur within data communications networks. Generally, a network loop is a configuration anomaly within a set of data communications devices that could cause packets to follow an endless loop within the network. As an example, the packets would move from router to router in a circle and never leave the network. Over time, the number of packets traveling in this loop would accumulate to the point that the routers in the loop would suffer from performance degradation and become unable to route non-looping packets in a timely manner. To overcome this drawback, data communications engineers added a time to live field in packet headers. The contents of the time to live field of a packet indicates a time a packet is allowed to live on the network. Network devices simulate passage of time by decrementing this field at each hop.
To use the time to live of a packet, when a source computer sends a packet to a target computer along a path of routers, the source computer initializes the contents of the time to live field of the packet to an initial value (e.g., between 0 and 255) prior to sending the packet along the path toward the target computer. Many common communications protocols set the initial value of the time to live field to be high enough to ensure that the packet will reach its intended destination. Common initial time to live values are 64 or 128. Each router to receive the packet decrements the contents of the time to live field of the packet, and determines whether the packet is stale by comparing the decremented contents to a predetermined value (e.g., 0 or 1). If the packet is stale, the router removes the packet from the network and sends an Internet Control Message Protocol (ICMP) error message back to the source computer (identified in the source address of the packet) to indicate that the router has removed the packet from the network. However, if the packet is not stale, the router forwards the packet to the next router or “hop” (as determined by packet routing protocols) along the network path leading to the target computer. The next router then processes the packet in a similar manner, and so on, until the packet arrives at the target computer, or until a router along the path removes the packet because the packet has become stale. Accordingly, any packet which is endlessly caught in a loop inevitably will become stale (as routers decrement its time to live field contents) and be removed from the network by a router.
Many conventional computer systems include, as part of their operating system, a “trace route” utility that allows a system administrator or other user of the computer to trace a route from one computer to another address on a network. Generally, the trace route utility identifies nodes that form a network path from the source computer to the target computer. Trace route relies on the above-described time to live feature of packets to identify each hop on the network path or route between two computers. To use trace route, at a source computer, a system administrator invokes the trace route utility and specifies a destination address. In response, trace route generates a packet and sets the time to live field of that packet initially to 1. Trace route then sends that packet onto the network from the source computer to the target or destination computer. Assuming that the first data communications device to receive the packet is a node other than the target computer, the first data communications device receiving the packet decrements the contents of the time to live field and determines that the packet is stale (e.g., the time to live contents now equal 0). Accordingly, the first data communications device removes the packet from the network and sends an Internet Control Messaging Protocol (ICMP) message back to the source computer (as identified by the source address in the packet originated by trace route). The source computer receives this ICMP message and is able to identify the first data communications device along the path leading to the target computer (e.g., from source address information in the header of the ICMP error message), and the round trip time (e.g., by calculating the difference between the time the source computer sends the packet and the time the source computer receives the ICMP error message.
The source computer then generates another trace route packet and sets the time to live field of that packet to 2. The source computer then sends that packet toward the target computer along the path. When the first data communications device receives that packet, the first data communications device decrements the contents of the time to live field and determines that the packet is not stale (e.g., the time to live contents are greater than 0). Accordingly, the first data communications device identifies a next or second data communications device on the path leading to the target computer, and sends the packet to the second data communications device. When the second data communications device receives and processes the packet, the second data communications device determines that the packet is now stale, removes the packet from the network, and sends an ICMP error message back to the source computer. The source computer processes this ICMP error message to identify the second router and an determine the round trip time for the packet.
The source computer continues to (i) generate packets with time to live fields having higher and higher values, and (ii) send those packets toward the target computer until the target computer finally receives a packet and does not respond with an ICMP error message (e.g., the target computer can respond with an acknowledgement message). The series of ICMP error messages that the source computer receives prior to reaching the target computer enable the source computer to identify the sequence of data communications devices (i.e. by address) that packets travel along the path or route leading from the source computer to the target computer (assuming that the path did not change during the route tracing process).